/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann Tübingen, Germany 
 * Niko Schenk Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl.visitors;

import util.Interval;
import saphre.core.Store;
import saphre.core.SuffixArray;
import java.util.List;

import util.IntString;

/**
 * Basic depth first traversal. Collects all phrases (maximal repeats) 
 * but no associated statistics such as tf or df.
 * 
 * @author Dale Gerdemann
 */
public class DepthFirstTraversal {

    static int minLengthOfMaximalPhrase = 1;
    static int maxLengthOfMaximalPhrase = 12;
    static int supermaximalcount = 0;

    // depth first traversal of lcp-interval tree
    public static int td(Interval inter, int lcp,
            SuffixArray sa, Store store, List<IntString> result,
            List<String> info) {

        if (!inter.trivial()) {
            int mid = sa.cldtab[inter.lb()];
            if (mid <= inter.lb() || mid > inter.rb()) {
                mid = sa.cldtab[inter.rb()];
            }
            Interval left = new Interval(inter.lb(), mid - 1);
            Interval right = new Interval(mid, inter.rb());
            if (lcp < sa.lcptab[mid]) {
                lcp = sa.lcptab[mid];
                boolean leftVariable = false;
                // niko.
                //boolean leftVariation = inter.leftVariation(lcp, sa, sa.text);
                //System.out.println("leftVariation. " + leftVariation);

                int b = store.text[sa.suftab[inter.lb()] - 1];
                for (int i = inter.lb() + 1; i <= inter.rb(); i++) {
                    if (store.text[sa.suftab[i] - 1] != b) {
                        leftVariable = true;
                        break;
                    }
                }
                if (leftVariable && lcp >= minLengthOfMaximalPhrase && lcp <= maxLengthOfMaximalPhrase) {
                    int loc = sa.suftab[inter.lb()];
                    result.add(store.toIntString(loc, loc + lcp));
                    String ngram = store.toString(loc, (loc + lcp));
                    System.out.println("maximal: " + ngram);
                    info.add("" + inter.tf());

                    // supermax 
                    boolean isSupermaximal = isSupermaximal(inter, sa, lcp);
                    if (isSupermaximal) {
                        System.out.println("-> supermaximal: " + ngram + " -- tf: " + inter.tf() + " " + inter.docDist(sa, store));
                        supermaximalcount++;
                    }
                }
            }
            td(left, lcp, sa, store, result, info);
            td(right, lcp, sa, store, result, info);
        }

        return supermaximalcount;
    }

    /**
     * Check if a maximal string is also supermaximal.
     *
     * @param inter
     * @param sa
     * @param lcp
     * @return
     */
    private static boolean isSupermaximal(Interval inter, SuffixArray sa, int lcp) {

        int[] sequence = sa.text;
        int[] suffixTable = sa.suftab;

        int left = inter.lb();
        int right = inter.rb();

        // System.out.println("Checking: " + left + " " + right);

        for (int i = left; i <= right; i++) {
            for (int j = left; j <= right; j++) {
                // compare nodes.
                if (i != j) {
                    // System.out.println("node i: " + i + "!= node j:" + j);
                    int iLoc = suffixTable[i];
                    int jLoc = suffixTable[j];
                    // System.out.println("iLoc: " + iLoc + ", jLoc: "+ jLoc);
                    int iSym = sequence[iLoc - 1];
                    int jSym = sequence[jLoc - 1];
                    // System.out.println("iSym: " + iSym + ", jSym: "+ jSym);
                    if (iSym == jSym) {
                        //System.out.println("abbruch.");
                        return false;
                    }

                    int iForward = sequence[iLoc + lcp];
                    int jForward = sequence[jLoc + lcp];
//                    System.out.println("iForward: " + iForward + ", jForward: "+ jForward);
                    if (iForward == jForward) {
//                        System.out.println("abbruch.");
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
